vector <int> zzf(string& s)
	// z-function from string
{
	vector <int> answer(s.length());
	answer[0] = 0;
	int l = 0, r = -1;
	for (int i = 1; i < s.length(); i++)
	{
		if (i > r)
			// then search naively, pushing bound R
		{
			int temp = 0;
			while (i + temp < s.length() && s[i + temp] == s[temp])
				temp++;
			answer[i] = temp;
			l = i; r = i + temp - 1;
		}
		else if (answer[i - l] <= r - i + 1)
			// obvious
			answer[i] = answer[i - l];
		else
			// searching naively, pushing bound R by the way
		{
			int temp = answer[i - l];
			while (i + temp < s.length() && s[i + temp] == s[temp])
				temp++;
			answer[i] = temp;
			l = i; r = l + temp - 1;
		}
	}
	answer[0] = s.length();
	return answer;
}
